package 领扣算法.力扣计划.算法基础.省份数量;

import java.util.HashSet;
import java.util.LinkedList;

public class Main {
    public int findCircleNum(int[][] isConnected) {
        HashSet<Integer> data=new HashSet<>();
        for (int i = 0; i < isConnected.length; i++) {
            data.add(i);
        }
        int res=0;
        for (int i = 0; i < isConnected.length; i++) {
            if (data.contains(i)){
                res++;
                plus(isConnected,data,i);
            }
        }
        return res;
    }

    private void plus(int[][] isConnected, HashSet<Integer> data, int i) {
        LinkedList<Integer> middle=new LinkedList<>();
        middle.addLast(i);
        HashSet<Integer> flag=new HashSet<>();
        flag.add(i);
        while (!middle.isEmpty())
        {
            i=middle.pollFirst();
            for (int j = 0; j < isConnected.length; j++) {
                if (isConnected[i][j]==1){
                    if(!flag.contains(j))
                    {
                        flag.add(j);
                        middle.addLast(j);
                    }
                }
            }
        }
        data.removeAll(flag);

    }
}
